public class Solution304 {

    int[][] sum;

    public Solution304(int[][] matrix) {
        sum=new int[matrix.length+1][matrix[0].length+1];
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                sum[i+1][j+1]=matrix[i][j]+sum[i][j+1]+sum[i+1][j]-sum[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2+1][col2+1]-sum[row2+1][col1]-sum[row1][col2+1]+sum[row1][col1];
    }

    public static void main(String[] args) {
        Solution304 solution304=new Solution304(new int[][]{{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}});
        System.out.println(solution304.sumRegion(2,1,4,3));
        System.out.println(solution304.sumRegion(1,1,2,2));
        System.out.println(solution304.sumRegion(1,2,2,4));
    }
}
